package com.peng.leetcode.heap;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * FindKthLargest
 * 215. 数组中的第K个最大元素
 *
 * @author: lupeng6
 * @create: 2020/12/11 17:49
 */
public class FindKthLargest {

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println(new Solution1().findKthLargest(arr, k));
    }

    static class Solution {
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length, (a, b) -> b - a);
            Arrays.stream(nums).forEach(queue::offer);
            for (int i = 0; i < k - 1; i++) {
                queue.poll();
            }
            return queue.poll();
        }
    }

    static class Solution1 {
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> a - b);
            for (int i = 0; i < k; i++) {
                queue.offer(nums[i]);
            }
            for (int i = k; i < nums.length; i++) {
                Integer heapTop = queue.peek();
                int num = nums[i];
                if (num > heapTop) {
                    queue.poll();
                    queue.offer(nums[i]);
                }
            }
            return queue.poll();
        }
    }
}
